1. Field of the Invention
The present invention relates to techniques for improving the performance of computer systems. More specifically, the present invention relates to a method and an apparatus for delaying memory accesses from other threads that interfere with on-going transactional program execution.
2. Related Art
Computer system designers are presently developing mechanisms to support multi-threading within the latest generation of Chip-Multiprocessors (CMPs) as well as more traditional Shared Memory Multiprocessors (SMPs). With proper hardware support, multi-threading can dramatically increase the performance of numerous applications. However, as microprocessor performance continues to increase, the time spent synchronizing between threads (processes) is becoming a large fraction of overall execution time. In fact, as multi-threaded applications begin to use even more threads, this synchronization overhead becomes the dominant factor in limiting application performance.
From a programmer's perspective, synchronization is generally accomplished through the use locks. A lock is typically acquired before a thread enters a critical section of code, and is released after the thread exits the critical section. If another thread wants to enter the same critical section, it must acquire the same lock. If it is unable to acquire the lock, because a preceding thread has grabbed the lock, the thread must wait until the preceding thread releases the lock. (Note that a lock can be implemented in a number of ways, such as through atomic operations or semaphores.)
Unfortunately, the process of acquiring a lock and the process of releasing a lock are very time-consuming in modern microprocessors. They involve atomic operations, which typically flush the load buffer and store buffer, and can consequently require hundreds, if not thousands, of processor cycles to complete.
Moreover, as multi-threaded applications use more threads, more locks are required. For example, if multiple threads need to access a shared data structure, it is impractical for performance reasons to use a single lock for the entire data structure. Instead, it is preferable to use multiple fine-grained locks to lock small portions of the data structure. This allows multiple threads to operate on different portions of the data structure in parallel. However, it also requires a single thread to acquire and release multiple locks in order to access different portions of the data structure.
In some cases, locks are used when they are not required. For example, many applications make use of “thread-safe” library routines that use locks to ensure that they are “thread-safe” for multi-threaded applications. Unfortunately, the overhead involved in acquiring and releasing these locks is still incurred, even when the thread-safe library routines are called by a single-threaded application.
Applications typically use locks to ensure mutual exclusion within critical sections of code. However, in many cases threads will not interfere with each other, even if they are allowed to execute a critical section simultaneously. In these cases, mutual exclusion is used to prevent the unlikely case in which threads actually interfere with each other. Consequently, in these cases, the overhead involved in acquiring and releasing locks is largely wasted.
Hence, what is needed is a method and an apparatus that reduces the overhead involved in manipulating locks when accessing critical sections.
One technique to reduce the overhead involved in manipulating locks is to “transactionally” execute a critical section, wherein changes made during the transactional execution are not committed to the architectural state of the processor until the transactional execution successfully completes. This technique is described in related U.S. patent application Ser. No. 10/637,168, entitled, “Selectively Monitoring Loads to Support Transactional Program Execution,” by inventors Marc Tremblay, Quinn A. Jacobson and Shailender Chaudhry, filed on 8 Aug. 2003.
During transactional execution, load and store operations are modified so that they mark cache lines that are accessed during the transactional execution. This allows the computer system to determine if an interfering data access occurs during the transactional execution. If so, the transactional execution fails, and results of the transactional execution are not committed to the architectural state of the processor. One the other hand, if the transactional execution successfully executes a block of instructions, results of the transactional execution are atomically committed to the architectural state of the processor.
Unfortunately, this commit operation does not happen instantaneously. During the commit operation, stores that took place during transactional execution must somehow be committed to the architectural state of the processor. Note that there can potentially be a large number of stores, so committing these stores can take a significant amount of time. While the stores are being committed, an interfering data access from another thread can potentially occur. However, failing the transactional execution to deal with this type of interfering data access during the commit operation is not a viable option, because doing so can leave the processor in an inconsistent state, with only a portion of the transactional updates committed.
Hence, what is needed is a method and an apparatus for preventing accesses from other threads from interfering with transactional program execution, and in particular that prevents accesses from other threads from interfering with a commit operation that takes place at the end of transactional program execution.